package com.gxc.linkedList;

import java.util.Stack;

public class Loopback {

    public static void main(String[] args) {
        Node one = Loopback.createNode();

        //用栈判断回环
        System.out.println(stackLoopBack(one));
        Node node = fastSlow(one);
        System.out.println( "value:" + node .value+",mid:"+ node.mid);
        node = fastSlow2(one);
        System.out.println( "value:" + node .value+",mid:"+ node.mid);
        node = fastSlow3(one);
        System.out.println( "value:" + node .value+",mid:"+ node.mid);
        node = fastSlow4(one);
        System.out.println( "value:" + node .value+",mid:"+ node.mid);

        //链表不增加额外空间，通过本身指针放下调转，来判断回环
        System.out.println(partition(one));
    }

    /**
     * 用栈判断回环
     * @param head
     */
    private static boolean stackLoopBack(Node head) {
        if (head == null) return false;
        Stack<Node> stack = createStack(head);

        while (!stack.empty()) {
            Node pop = stack.pop();
            if (pop.value == head.value) {
                head = head.next;
            } else {
                return false;
            }
        }
        return true;
    }

    private static Stack<Node> createStack(Node head) {
        Stack<Node> stack = new Stack<>();
        while (head!=null) {
            stack.push(head);
            head = head.next;
        }
        return stack;
    }

    /**
     * 快慢指针找链表终点
     * 奇数个节点为中点
     * 偶数个节点为上中点
     * @param head
     * @return
     */
    private static Node fastSlow(Node head) {
        if (head == null) return null;
        Node fast = head;
        Node slow = head;

        while (fast.next!=null && fast.next.next!=null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow;
    }

    /**
     * 快慢指针找链表终点
     * 奇数个节点为中点
     * 偶数个节点为下中点
     * @param head
     * @return
     */
    private static Node fastSlow2(Node head) {
        if (head == null) return null;
        Node fast = head;
        Node slow = head;

        while (fast!=null && fast.next!=null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow;
    }

    /**
     * 快慢指针找链表终点
     * 奇数个节点为中点
     * 偶数个节点为上中点的前驱节点
     * @param head
     * @return
     */
    private static Node fastSlow3(Node head) {
        if (head == null) return null;
        Node fast = head;
        Node slow = head;
        Node prev = null;

        while (fast.next!=null && fast.next.next!=null) {
            prev = slow;
            fast = fast.next.next;
            slow = slow.next;
        }
        return prev;
    }

    /**
     * 快慢指针找链表终点
     * 奇数个节点为中点
     * 偶数个节点为下中点的前驱节点
     * @param head
     * @return
     */
    private static Node fastSlow4(Node head) {
        if (head == null) return null;
        Node fast = head;
        Node slow = head;
        Node prev = null;

        while (fast!=null && fast.next!=null) {
            prev = slow;
            fast = fast.next.next;
            slow = slow.next;
        }
        return prev;
    }

    /**
     * 链表额外空间复杂度为O(1)，通过本身指针反向，来判断回环
     * @param head
     * @return
     */
    private static boolean partition(Node head) {
        Node mid = fastSlow(head);

        //中点后的链表反向
        Node prev = null;
        Node current = mid.next;
        mid.next = null;
        Node next;
        while (current!=null) {
            //保存当前节点的下一个节点
            next = current.next;
            //当前节点的下一个节点修改为前节点
            current.next = prev;
            //当前节点修改为前节点
            prev = current;
            //下一个节点修改为当前节点
            current = next;
        }

        Node first = head;
        next = prev;
        while (first!=null && next!=null) {
            if (first.value!=next.value) return false;
            first = first.next;
            next = next.next;
        }

        //中点后的链表还原
        current = prev;
        prev = null;
        while (current!=null) {
            //保存当前节点的下一个节点
            next = current.next;
            //当前节点的下一个节点修改为前节点
            current.next = prev;
            //当前节点修改为前节点
            prev = current;
            //下一个节点修改为当前节点
            current = next;
        }
        mid.next = prev;
        return true;
    }

    /**
     * 非环链表
     * @return
     */
    public static Node createNode() {
        Node one = new Node(1);
        Node two = new Node(2);
        Node three = new Node(3, 0);
        Node four = new Node(3, 1);
        Node five = new Node(2);
        Node six = new Node(1);

        one.next = two;
        two.next = three;
        three.next = four;
        four.next = five;
        five.next = six;

        return one;
    }

    /**
     * 环链表
     * @return
     */
    public static Node createRingNode() {
        Node one = new Node(1);
        Node two = new Node(2);
        Node three = new Node(3, 0);
        Node four = new Node(4, 1);
        Node five = new Node(5);
        Node six = new Node(6);

        one.next = two;
        two.next = three;
        three.next = four;
        four.next = five;
        five.next = six;

        Node round1 = new Node(7);
        Node round2 = new Node(8);
        Node round3 = new Node(9);
        Node round4 = new Node(10);
        six.next = round1;
        round1.next = round2;
        round2.next = round3;
        round3.next = round4;
        round4.next = four;

        return one;
    }

}
